package sort;

public class HeapSort implements ISort{

	private int heapArrLen = 0;

	public void sort(int[] arr) {
		heapArrLen = arr.length;
		while (heapArrLen > 1) {
			int lastParentNode = heapArrLen / 2 - 1;
			for (int i = lastParentNode; i >= 0; i--) {
				adjustNode(arr, i);
			}
			int tmp = arr[0];
			arr[0] = arr[heapArrLen - 1];
			arr[heapArrLen - 1] = tmp;
			heapArrLen--;
		}
	}

	public void adjustNode(int[] arr, int index) {
		int leftChild = index * 2 + 1;
		int rightChild = index * 2 + 2;
		if (leftChild < heapArrLen) {
			if (arr[leftChild] > arr[index]) {
				int tmp = arr[index];
				arr[index] = arr[leftChild];
				arr[leftChild] = tmp;
				adjustNode(arr, leftChild);
			}
		} else {
			return;
		}
		if (rightChild < heapArrLen) {
			if (arr[rightChild] > arr[index]) {
				int tmp = arr[index];
				arr[index] = arr[rightChild];
				arr[rightChild] = tmp;
				adjustNode(arr, rightChild);
			}
		} else {
			return;
		}
	}

	public static void main(String[] args) {
		HeapSort heapSort = new HeapSort();
		int arr[] = { 8, 4, 7, 9, 6, 3, 1, 2, 5 };
		heapSort.sort(arr);
		ISort.printArr(arr);
	}

}
